//
// Created by zuo on 2024/6/29.
//

#include <algorithm>
#include<iostream>
#include<vector>

using namespace std;

// binary_search 单调就能用 sort 一下就能用
// lower_bound 和 upper_bound  必须先用一下sort  变成 非降序 序列才能用
// binary_search(起始地址，终止地址，目标值)  布尔类型  找到1 没找到0

// lower_bound(st,ed,x) 返回地址[st,ed)中 第一个 >= x 的元素的 地址   地址 - 首地址 = 下标
// upper_bound(st,ed,x) 返回地址[st,ed)中 第一个 > x 的元素的 地址   地址 - 首地址 = 下标
// 1 2 3 8 8 8 9 10  8的上界和下界就是 [lower_bound,upper_bound)

int main()
{
    vector<int> v = {1, 5, 2, 8, 6, 7, 9, 3, 4, 8, 8, 12, 11};
    int target1 = 5;
    int target2 = 10;
    sort(v.begin(), v.end()); // 升序  非降序
    bool found1 = binary_search(v.begin(), v.end(), target1);
    if (found1) cout << target1 << " found" << '\n';
    else cout << target1 << " not found" << '\n';

    bool found2 = binary_search(v.begin(), v.end(), target2);
    if (found2) cout << target2 << " found" << '\n';
    else cout << target2 << " not found" << '\n';

    //找到数组中8的元素的上界和下界
    cout << (lower_bound(v.begin(), v.end(), 8) - v.begin()) << '\n';
    cout << (upper_bound(v.begin(), v.end(), 8) - v.begin()) << '\n';

    return 0;
}
